The present invention is directed to image processing. It finds particular, but not exclusive, application in photocopiers.
Photocopying is an example of a class of image-processing applications in which proper alignment of an input image is necessary or at least desirable. In most cases, alignment of an of an original document on a photocopier bed is easy: it is a relatively simple matter to have the document original abut the edge of the photocopier""s scanner bed so as to align its top and bottom edges with ruled indicia provided for that purpose.
But alignment is harder when the user wants to take a composite image of a number of small documents, such as a check and the associated receipt, the front and back of a check, several photographs, etc. In these situations, the user cannot abut all of the documents against the scanner bed""s edge, or may not want to, and the scanner-bed indicia are typically not designed to align smaller-sized documents. So the user must align the documents by visual impression only, and the results are only occasionally satisfactory. It would therefore be desirable for the photocopier to include a feature by which it automatically aligns documents to give the resultant composite image a pleasing appearance.
U.S. Pat. Nos. 5,430,550 and 5,440,403 to Hashimoto et al. propose an approach to a similar problem. The problem faced there involves an input image taken from, say, a microfilm transparency containing a number of individual microfilm frames. The transparency may not be aligned properly with the imaging device, and it may be desired to display the individual frames in relative positions different from those that they occupy on the input transparency. The Hashimoto et al. approach to identifying the constituent components and determining their skew angle vis-à-vis the input scan orientation is to find the first and second locations in each of a plurality of scan lines where transitions occur between bright, indicating a blank transparency region with no frame present, to darker, indicating the presence of a frame. These two locations will indicate the places where the two frames begin. The frames"" skew angle can be determined by the differences between where these transitions occur in different scans.
The approach described in the Hashimoto et al. patents has the virtue of simplicity. Whatever its applicability to microfilm transparencies may be, however, it is not well suited to the problem described above, where the types of input images vary more in size and position, and contrast is not as great between document and no-document locations.
We have arrived at an approach that yields good results in the more-difficult applications described above. In accordance with our approach, constituent input sub-images of the input composite image are independently de-skewed, by angles that are not the same in general, to produce corresponding constituent sub-images of the output image. The sub-images are identified by using what we call xe2x80x9ccomponentsxe2x80x9d of a xe2x80x9cpreviewxe2x80x9d version of the image. The preview image can be the image itself but is more commonly a lower-resolution version of that image. A component is a xe2x80x9cconnected groupxe2x80x9d of the preview image""s pixels that meet certain pixel-qualifying criteria based on the values of those pixels and/or of pixels in their neighborhoods. A pixel-qualifying criterion that we use in one embodiment, for instance, is that the image""s gradient magnitude at the pixel""s location exceeds a predetermined threshold after that image has been subjected to unsharp masking.
As used here, a connected group of qualifying pixels is one in which each group member is xe2x80x9cconnectedxe2x80x9d to all others. A first qualifying pixel in a group is connected to a second pixel in the group if (1) the first and second qualifying pixels meet a predetermined proximity criterion or (2) the first pixel meets the predetermined proximity criterion with a qualifying pixel that is connected to the second qualifying pixel. For present purposes, a proximity criterion is one met by some of the image""s pixel pairs and not by others and for which there exist maximum and minimum distances such that the proximity criterion is not met by any pixel pair whose pixels"" positions differ by more than the maximum distance but is met by each pixel pair whose pixels"" positions differ by less than the minimum distance. The proximity criterion employed here is that the two pixels must be contiguous, but other proximity criteria can be used instead.
Components that meet certain component-qualifying criteria are assigned respective de-skewing angles and employed to define the input sub-images that are separately de-skewed. More specifically, a predetermined bounding rule is used to associate with each qualifying component an input-composite-image bounding region that includes all of the component""s pixels. This bounding region contains the part of the input composite image that is de-skewed in accordance with that component""s de-skewing angle to produce the output composite image""s constituent sub-images.
In accordance with the present invention, one of the component-qualifying criteria is that a second bounding region of the composite input image determined in accordance with a second bounding rule from a given component not be contained completely within a third bounding region, determined in accordance with a third bounding rule from any other component. In the embodiment to be described below, the second and third bounding rules are the same, so the bounding regions determined in accordance with them from a given component are, too.